package 分成互质组;

import java.util.Scanner;

public class Main {
    static int N = 15, n;
    static int ans = N;
    static int[] a = new int[N];
    static boolean[] st = new boolean[N];
    static int[][] group = new int[N][N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        dfs(1, 0, 0, 0);
        System.out.println(ans);
    }

    private static void dfs(int g, int u, int cnt, int start) {
        if (g >= ans) {
            return;
        }
        if (cnt == n) {
            ans = g;
        }
        boolean flag = true;
        for (int i = start; i < n; i++) {
            if (!st[i] && check(g, u, i)) {
                st[i] = true;
                group[g][u] = i;
                dfs(g, u + 1, cnt + 1, i + 1);
                st[i] = false;
                group[g][u] = 0;
                flag = false;
            }
        }
        if (flag) {
            dfs(g + 1, 0, cnt, 0);
        }
    }

    private static boolean check(int g, int u, int i) {
        for (int j = 0; j < u; j++) {
            if (gcd(a[group[g][j]], a[i]) > 1) {
                return false;
            }
        }
        return true;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
